package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/14 10:27
 *
 *
 * 数字在升序数组中出现的次数
 [1,2,3,3,3,3,4,5],3
 4

 二分查找：因为是整数，所以查找他两边的小数，即可算得出现次数
 */

public class Main24 {
    public  int bsL(int []a,int k){
        int l=0,r=a.length-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(a[mid]>=k)r=mid;
            else l=mid+1;
        }
        return l;
    }

    public  int bsR(int []a,int k){
        int l=0,r=a.length-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(a[mid]<=k)l=mid;
            else r=mid-1;//如果不加1，则当r=l+1时就会死循环
        }
        return l;
    }


    public int bs(int []a,double k){
        int l=0,r=a.length-1;
        while (l<r){
            int mid=(l+r)>>1;
            if(a[mid]>k)r=mid-1;
            else l=mid+1;
        }
        return l;
    }

    public int GetNumberOfK(int [] array , int k) {
        if(array.length==0)return 0;
         return bs(array,k+0.5)-bs(array,k-0.5);
    }
    public static void main(String[] args) {
        int arr[]={1,2,3,3,3,3,4,5};
        System.out.println(new Main24().GetNumberOfK(arr,3));
    }
}
